package com.larry;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;

/**
 * @ProjectName algorithm
 * @Author larry
 * @Date 15:07 2021/7/23
 * @Description 三数之和
 **/
public class ThreeSum {

    //暴力法       时间复杂度O(n³)
    public static List<List<Integer>> test1(int[] nums){
        int n = nums.length;
        ArrayList<List<Integer>> result = new ArrayList<>();

        for (int i = 0; i < n - 2; i++) {
            for (int j = i + 1; j < n -1; j++) {
                for (int k = j + 1; k < n; k++) {
                    if (nums[i] + nums[j] + nums[k] == 0){
                        result.add(Arrays.asList(nums[i],nums[j],nums[k]));
                    }
                }
            }
        }
        return result;
    }

    //hash       时间复杂度O(n²)
    public static List<List<Integer>> test2(int[] nums){
        int n = nums.length;
        ArrayList<List<Integer>> result = new ArrayList<>();

        HashMap<Integer, List<Integer>> map = new HashMap<>();

        return result;
    }

    //双指针       时间复杂度O(n²)
    public static List<List<Integer>> test3(int[] nums){
        int n = nums.length;
        ArrayList<List<Integer>> result = new ArrayList<>();

        //对数组进行排序
        Arrays.sort(nums);

        //遍历每一个元素，作为三元组中最小的那个
        for (int i = 0; i < n; i++) {
            //如果当前数大于0，直接退出循环
            if (nums[i] > 0){
                break;
            }
            //如果当前数据已经出现过，直接跳过
            if (i > 0 &&nums[i] == nums[i-1]){
                continue;
            }
            //定义左右指针
            int lp = i + 1;
            int rp = n - 1;
            while (lp < rp){
                int sum = nums[i] + nums[lp] + nums[rp];
                if (sum == 0){
                    result.add(Arrays.asList(nums[i],nums[lp],nums[rp]));
                    lp++;
                    rp--;
                }else if (sum < 0){
                    lp++;
                }else {
                    rp--;
                }
            }
        }
        return result;
    }

    public static void main(String[] args) {
        int[] input = {-1,0,1,2,-1,-4};
        List<List<Integer>> list = ThreeSum.test3(input);
        System.out.println(list.toString());
    }

}
